#include <iostream>
#include <vector>
#include <queue>
#include "euler.h"

BEGIN_PROBLEM(247, solve_problem_247)
	PROBLEM_TITLE("Squares under a hyperbola")
	PROBLEM_ANSWER("782252")
	PROBLEM_DIFFICULTY(2)
	PROBLEM_FUN_LEVEL(3)
	PROBLEM_TIME_COMPLEXITY("n")
	PROBLEM_SPACE_COMPLEXITY("n")
	PROBLEM_KEYWORDS("geometry")
END_PROBLEM()

// Returns the side length of the largest square that fits under the
// hyperbola xy = 1, constrained by x >= x0 and y >= y0.
static double largest_square_size(double x0, double y0)
{
	return (std::sqrt((x0-y0)*(x0-y0)+4.0)-(x0+y0))/2.0;
}

// Each segment on the hyperbola is marked with squares on its end points.
// It also stores the side length of the largest square that fits under
// this segment.
struct segment
{
	double x0;   // constraint: x >= x0
	double y0;   // constraint: y >= y0
	int left;    // id of the square whose upper-right vertex is the left point
	int right;   // id of the square whose upper-right vertex is the right point
	double size; // side length of the largest square that fits in this segment
	
	segment(double _x0, double _y0, int _left, int _right)
		: x0(_x0), y0(_y0), left(_left), right(_right), 
		size(largest_square_size(_x0, _y0)) { }
};

// Order the segments by the potential square size.
static bool operator < (const segment &s1, const segment &s2)
{
	return s1.size < s2.size;
}

static void solve_problem_247()
{
	int verbose = 0;

	// Stores the (left,below) index of each square in a list.
	struct square
	{
		int nleft;  // number of squares to the left
		int nbelow; // number of squares below

		square(int _left, int _below) : nleft(_left), nbelow(_below) { }
	};
	std::vector<square> squares;

	// Since square ID needs to start at one, we put a dummy square at ID 0.
	squares.push_back(square(-1, -1));

	// Store the segments in a priority queue ordered by the largest square
	// that would fit in.
	std::priority_queue<segment> segments;

	// Initialize the segment list with the entire hyperbola.
	segment s0(1.0, 0.0, 0, 0);
	segments.push(s0);

	// Give a threashold of the maximum (left,below) index of the square
	// to generate.
#if 0
	int max_left = 1, max_below = 1;
#else
	int max_left = 3, max_below = 3;
#endif

	// Keep track of the remaining number of segments whose fitting square
	// would have an index within (max_left,max_below).
	int remaining = 1; 

	// Loop through the segments.
	while (remaining > 0)
	{
		// Fetch the largest segment.
		segment s = segments.top();
		segments.pop();

		// Create the largest square that fits in this segment.
		square sq(squares[s.left].nleft+1, squares[s.right].nbelow+1);

#if 1
		// Check if the (left,below) index of the new square is within the 
		// threshold. If it is, decrement the _remaining_ counter, and
		// check if the two new segments would contain squares with index
		// within the threshold.
		if (sq.nleft <= max_left && sq.nbelow <= max_below)
		{
			--remaining;
			if (sq.nleft < max_left)
				++remaining;
			if (sq.nbelow < max_below)
				++remaining;
		}
#else
		// Check if the (left,below) index of the new square is within the 
		// threshold. If not, any further squares created within this 
		// segment will exceed the threshold as well. So we don't need to
		// proceed.
		if (sq.nleft > max_left || sq.nbelow > max_below)
			continue;
#endif

		// Append the square into the square list.
		int square_id = (int)squares.size();
		squares.push_back(sq);
		if (verbose >= 2)
		{
			double x = s.x0 + s.size, y = s.y0 + s.size;
			std::cout << "Square " << square_id << " (" << sq.nleft 
				<< ", " << sq.nbelow << "): (" 
				<< x << ", " << y << "), size=" << s.size << std::endl;
		}

		// Split the segment into two sub-segments.
		segment s1(s.x0, s.y0 + s.size, s.left, square_id);
		segment s2(s.x0 + s.size, s.y0, square_id, s.right);
		segments.push(s1);
		segments.push(s2);
	}

	// The last square in the list is the smallest square with index 
	// (left,below).
	int id = (int)squares.size() - 1;
	if (verbose >= 1)
	{
		std::cout << "Index of last square: " << id << std::endl;
	}
	else
	{
		std::cout << id << std::endl;
	}
}
